package com.zwj.interview.二进制;

import java.util.Arrays;

/**
 * 输入一个非负数n，请计算0到n之间每个数字的二进制形式中1的个数，并输出一个数组。
 * 例如，输入的n为4，由于0、1、2、3、4的二进制形式中1的个数分别为0、1、1、2、1，因此输出数组[0，1，1，2，1]
 */
public class BinaryOneCount {


    /**
     * “i&（i-1）”将i的二进制形式中最右边的1变成0，也就是说，整数i的二进制形式中1的个数比“i&（i-1）”的二进制形式中1的个数多1
     *
     * @param num
     * @return
     */
    public int[] countBits(int num) {
        //result[0]的值为0
        int[] result = new int[num + 1];
        for (int i = 1; i <= num; ++i) {
            result[i] = result[i & (i - 1)] + 1;
        }
        return result;
    }

}



